package com.example.algorithm.tree;

import java.util.*;


// 此案例演示，如何按层遍历二叉树，然后一层一层分别打印出来。也可以用来求二叉树的深度。

// 这个是自己定义的一个类而已
// 在Java中，一个.java文件中可以包含多个类（或者接口），但是只能有一个公共类（public class），而且这个公共类的类名必须与文件名相同。
// 其他非公共类可以在同一个文件中声明，但不能声明为公共类。
// 它可以表示一个树。也可以表示一个节点。
// 看到没有，这个TreeNode定义的时候，是递归的。就是它的左右节点又分别是TreeNode类型的。
class TreeNode {

    int val; // 当前节点的值
    TreeNode left; // 当前节点的左节点
    TreeNode right; // 当前节点右节点的

    // 构造方法
    TreeNode(int x) {
        val = x;
    }
}


// 这是自己定义的另一个类，是public的。
// 按层来遍历一个二叉树。然后分别打印出每层。
public class LevelOrderTraversal {

    // 就是一个普通的二叉树而已。没有什么顺序。
    //    3
    //9       20
    //    15       7
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        // 这个是遍历的方法
        List<List<Integer>> result = levelOrder(root);
        // 这个是打印的方法
        printResult(result);
    }


    // TreeNode root 这其实就是一整个树了。
    public static List<List<Integer>> levelOrder(TreeNode root) {

        // 装每层的结果的
        List<List<Integer>> result = new ArrayList<>();
        // 根节点为空直接返回。此时的root就是整个树哦，实际调试打印看了。
        if (root == null) return result;

        // 声明了一个链表
        Queue<TreeNode> queue = new LinkedList<>();
        // queue.offer() 方法用于将指定的元素插入队列。当然是在最后插入啦。
        // 此时虽然root是一整个树结构，装了整个树。但是，我们起初给level 添加的时候，是看的val，还并不看左右。如下：
        // level.add(node.val);
        // 所以，此时的root，对于queue来说，它仅仅只是一个节点。装进queue，queue里面仅仅只有一个节点而已，size为1.
        // 至于其他的节点，那是root的left和right属性来着。对于queue来说，目前root仅仅是一个节点而已。
        queue.offer(root);

        // 只要queue不为空，就一直走。第一层循环。
        while (!queue.isEmpty()) {
            // 第一轮等于1，因为根节点本来只有一个。
            // 第二轮等于2，因为第二层有两个元素。
            // 第三轮也等于2，应为第三层有2个元素。没有第四轮。
            int size = queue.size();
            List<Integer> level = new ArrayList<>(); // 这是一层的数据

            // 第二层循环
            for (int i = 0; i < size; i++) {
                // queue.poll() 是 Queue 接口的一个方法，用于从队列中获取并移除队首的元素。如果队列为空，该方法返回 null。
                TreeNode node = queue.poll();
                level.add(node.val);
                // 当前节点的下一层都加入到queue里面。
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            // 这里面装所有层的数据
            result.add(level);
        }

        return result;
    }


    // Helper method to print the result
    public static void printResult(List<List<Integer>> result) {
        // Result装所有层的数据。现在在for循环出一层一层。level就是一层。
        for (List<Integer> level : result) {
            for (int num : level) {
                System.out.print(num + " ");
            }
            System.out.println(); // Print newline after each level。打印一行空格。
        }
    }
}


// 其他重要备注：

//本例中的queue为什么用LinkedList，而不用ArrayList呢
//
//在这个例子中，使用 `LinkedList` 而不是 `ArrayList` 是因为队列的操作主要是在队列的头部（移除元素）和尾部（添加元素）。
//`LinkedList` 实现了 `Queue` 接口，它具有高效的头部和尾部操作（即 `poll()` 和 `offer()` 方法）。
//相比之下，`ArrayList` 的头部操作（移除元素）是线性时间复杂度的，而 `LinkedList` 的头部操作则是常数时间复杂度的，因此更适合作为队列的实现。
// 注意，上面说的ArrayList是线性复杂度，其实也就是O(n)，其中n为列表的长度。其实呢，它说的是从队首拿出元素是线性复杂度。因为其他元素要平移啊。但是在队尾插入元素，其实ArryList是常数复杂度。
// 当然，如果是查询元素的话，按照索引来查询的话，那么ArrayList则是常数复杂度。

// LinkedList既实现了List接口，也实现Queue接口吗
//是的，`LinkedList` 类同时实现了 `List` 接口和 `Queue` 接口。这意味着你可以将其作为列表或队列来使用。
//作为列表时，你可以使用 `add()` 和 `get()` 等方法；
//作为队列时，你可以使用 `offer()`、`poll()` 和 `peek()` 等方法。

